package dp.Profit;
/**
 * @Date 2020/04/17
 * @author 王光浩
 * @Thinking 转化法
 */
public class MyMethodOne {
	public int maxProfit(int[] prices) {
		if(prices.length <=1 )return 0;
		int[] helper = new int[prices.length-1];
		//求出相邻元素之间的差值
		for(int i=0 ; i<prices.length-1 ; i++) {
			helper[i] = prices[i+1]-prices[i];
		}
		return helper(0,helper);
	}
	/**
	 * 返回自从 left 开始的最大利润
	 * @param left
	 * @param prices
	 * @return
	 */
	private int helper(int left,int[] prices) {
		if( left>=prices.length )return 0;
		int sum = 0;
		for(int i=left ; i<prices.length ; i++) {
			if( prices[i]<0 ) {
				if( i!=prices.length-1 && (prices[i-1]+prices[i]<0 || prices[i]+prices[i+1]<0) ) {
					int le = sum-prices[i-1]+helper(i+1,prices);
					int ri = sum+helper(i+2,prices);
					sum = Math.max(le, ri);
				}
				break;
			}
			sum += prices[i];
		}
		return sum;
	}
}
